package com.huwaiwai.algorithm.search;

public class Dichotomy {

    public static void main(String[] args) {
        int[] a = new int[100];
        for (int i = 0; i < 100; i++) {
            a[i] = i;
        }
        a[98] = 99;
        int indexV1 = v1(a, 99);
        System.out.println(indexV1);
        int indexV2 = v2(a, 99);
        System.out.println(indexV2);
        int indexV3 = v3(a, 50);
        System.out.println(indexV3);
        int indexV4 = v4(a, 50);
        System.out.println(indexV4);
    }


    // 查找第一个匹配元素的下标
    public static int v1(int[] a, int target) {
        int length = a.length;
        int s = 0;
        int e = length - 1;
        while (s <= e) {
            int mid = s + ((e - s) >> 1);
            int value = a[mid];

            if (value < target) {
                s = mid + 1;
            } else if (value > target) {
                s = mid + 1;
            } else {
                if (mid == 0 || a[mid - 1] < target) {
                    return mid;
                }
                e = mid - 1;
            }
        }
        return -1;
    }

    // 查找最后一个匹配元素的下标
    public static int v2(int[] a, int target) {
        int length = a.length;
        int s = 0;
        int e = length - 1;
        while (s <= e) {
            int mid = s + ((e - s) >> 1);
            int value = a[mid];

            if (value < target) {
                s = mid + 1;
            } else if (value > target) {
                s = mid + 1;
            } else {
                if (mid == length - 1 || a[mid + 1] > target) {
                    return mid;
                }
                s = mid + 1;
            }
        }
        return -1;
    }


    // 查找第一个大于等于给定值的元素的下标
    public static int v3(int[] a, int target) {
        int length = a.length;
        int s = 0;
        int e = length - 1;
        while (s <= e) {
            int mid = s + ((e - s) >> 1);
            int value = a[mid];
            if (value < target) {
                s = mid + 1;
            } else {
                if (mid == 0 || a[mid - 1] < target) {
                    return mid;
                }
                e = mid - 1;
            }
        }
        return -1;
    }

    // 查找最后一个小于等于给定值的元素的下标
    public static int v4(int[] a, int target) {
        int length = a.length;
        int s = 0;
        int e = length - 1;
        while (s <= e) {
            int mid = s + ((e - s) >> 1);
            int value = a[mid];
            if (value > target) {
                e = mid - 1;
            } else {
                if (mid == length - 1 || a[mid + 1] > target) {
                    return mid;
                }
                s = mid + 1;
            }
        }
        return -1;
    }
}
